package problems.daily;

/**
 * 1156. 单字符重复子串的最大长度
 * <p>https://leetcode.cn/problems/swap-for-longest-repeated-character-substring/</p>
 *
 * @author dubulingbo, 2023/6/3 15:28.
 */
public class DT1156 {
    public int maxRepOpt1(String text) {
        char[] chs = text.toCharArray();
        int n = chs.length;
        int[] cnt = new int[26];

        // 记录每个字符出现的次数
        for (char c : chs) ++cnt[c - 'a'];

        int ret = 0;
        int i = 0;
        while (i < n) {
            // 找出当前相同字符的一段[i, j)
            int j = i;
            while (j < n && chs[j] == chs[i]) ++j;

            // 当前这一段连续相同的字符串的长度
            int len = j - i;
            // len < 该字符出现的总数，并且前面或后面有空位，则可以替换，即长度为 len+1
            if (len < cnt[chs[i] - 'a'] && (j < n || i > 0))
                ret = Math.max(ret, len + 1);

            // 找到这一段后面与之【相隔一个不同字符】的另一段 [j+1, k)
            int k = j + 1;
            while (k < n && chs[k] == chs[i]) ++k;

            // 最大长度不会超过该字符出现的总次数
            ret = Math.max(ret, Math.min(k - i, cnt[chs[i] - 'a']));

            // 更新 i
            i = j;
        }

        return ret;
    }
}
